package test;
import java.util.HashSet;
import java.util.Random;

/**
 * 预生成短 URL
 * @author 豆包LU
 * @date 2023/4/28 15:26
 */
public class ShortUrlGenerator {
    private static final int SHORT_URL_LENGTH = 6;
    private static final String BASE_URL = "http://example.com/";

    private static final String[] CHARACTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_".split("");
    private static final int BASE = CHARACTERS.length;
    private static final int POOL_SIZE = 10000;

    private static final HashSet<String> urlPool = new HashSet<String>(POOL_SIZE);
    private static final BloomFilter bloomFilter = new BloomFilter(POOL_SIZE, 0.01);

    private static final Random random = new Random();

    public static void main(String[] args) {
        // 初始化URL池
        for (int i = 0; i < POOL_SIZE; i++) {
            String shortUrl = generateShortUrl();
            urlPool.add(shortUrl);
            bloomFilter.add(shortUrl);
        }

        // 生成测试用的长URL
        String longUrl = "http://www.example.com/articles/how-to-build-a-short-url-service";

        // 生成短URL
        String shortUrl = getShortUrl(longUrl);

        System.out.println("长URL：" + longUrl);
        System.out.println("短URL：" + shortUrl);
    }

    // 生成短URL
    private static String getShortUrl(String longUrl) {
        String shortUrl = generateShortUrl();

        // 判断生成的短URL是否已存在
        while (urlPool.contains(shortUrl) && bloomFilter.contains(shortUrl)) {
            shortUrl = generateShortUrl();
        }

        // 添加到URL池和布隆过滤器中
        urlPool.add(shortUrl);
        bloomFilter.add(shortUrl);

        return BASE_URL + shortUrl;
    }

    // 生成短URL字符串
    private static String generateShortUrl() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < SHORT_URL_LENGTH; i++) {
            int randomIndex = random.nextInt(BASE);
            sb.append(CHARACTERS[randomIndex]);
        }
        return sb.toString();
    }

    // 布隆过滤器实现
    static class BloomFilter {
        private boolean[] bits;
        private int size;
        private int hashFunctionCount;

        public BloomFilter(int size, double falsePositiveProbability) {
            this.size = size;
            bits = new boolean[size];
            hashFunctionCount = (int) Math.ceil(-Math.log(falsePositiveProbability) / Math.log(2));
        }

        private int[] hash(String element) {
            int[] hashes = new int[hashFunctionCount];
            int hash1 = element.hashCode();
            int hash2 = hash1 >>> 16;
            for (int i = 0; i < hashFunctionCount; i++) {
                int combinedHash = hash1 + i * hash2;
                if (combinedHash < 0) {
                    combinedHash = ~combinedHash;
                }
                hashes[i] = combinedHash % size;
            }
            return hashes;
        }

        public void add(String element) {
            int[] hashes = hash(element);
            for (int hash : hashes) {
                bits[hash] = true;
            }
        }

        public boolean contains(String element) {
            int[] hashes = hash(element);
            for (int hash : hashes) {
                if (!bits[hash]) {
                    return false;
                }
            }
            return true;
        }
    }
}

